package datasort.sorters;

/**
 * Created with IntelliJ IDEA.
 * User: platonovv
 * Date: 31.10.13
 */
public class QuickSort implements DataSorter<Integer> {

    public Integer[] sort(Integer[] data) {
        if (data == null)
            return null;
        if (data.length == 0)
            return data;
        Integer[] array = new Integer[data.length];
        System.arraycopy(data, 0, array, 0, data.length);
        sort(array, 0, data.length - 1);
        return array;
    }

    public Integer[] sort(Integer[] data, SortType type) {
        Integer[] array = sort(data);
        if (SortType.DESC.equals(type))
            reverse(array);
        return array;
    }

    private static void sort(Integer[] data, int l, int r) {
        int pivot = data[(l + r) / 2];
        int a = l;
        int b = r;
        while (a <= b) {
            while (data[a] < pivot) {
                a = a + 1;
            }
            while (data[b] > pivot) {
                b = b - 1;
            }
            if (a <= b) {
                swap(data, a, b);
                a = a + 1;
                b = b - 1;
            }
        }
        if (l < b) sort(data, l, b);
        if (b < r) sort(data, a, r);
    }

    private static void swap(Integer[] data, int i, int j) {
        int t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    private static void reverse(Integer[] data) {
        for (int i = 0; i < data.length / 2; i++) {
            int temp = data[i];
            data[i] = data[data.length - 1 - i];
            data[data.length - 1 - i] = temp;
        }
    }
}
